home *** CD-ROM | disk | FTP | other *** search
/ Mission 3 / Mission 3.zip / Mission 3.iso / texte / 7up_pd / sort.c < prev    next >
Text File  |  1998-10-29  |  12KB  |  474 lines
  1. /* Heap Sort */
  2. /*****************************************************************************
  3. *
  4. *                                              7UP
  5. *                                        Modul: SORT.C
  6. *                                     (c) by TheoSoft '91
  7. *
  8. *****************************************************************************/
  9. #include <portab.h>
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13. #include <ctype.h>
  14. #include <aes.h>
  15. #include <vdi.h>
  16.  
  17. #if GEMDOS
  18. #include <tos.h>
  19. #include <ext.h>
  20. #else
  21. #include <alloc.h>
  22. #include <dir.h>
  23. #endif
  24.  
  25. #include "alert.h"
  26.  
  27. #include "7up.h"
  28. #include "forms.h"
  29. #include "windows.h"
  30.  
  31. typedef struct
  32. {
  33.     int menu,item;
  34. } UNDO;
  35.  
  36. extern UNDO undo;
  37.  
  38. typedef struct
  39. {
  40.     char *str;
  41.     int used,len;
  42.     long line; /* beinhaltet die sortierte Reihenfolge, z.B. 3,4,0,2,1 */
  43.     int effect;
  44. }SORTSTRUCT;
  45.  
  46. static int col;
  47.  
  48. /*
  49.  * Heap sorting functions
  50.  */
  51.  
  52. static _nswap(register char *pa, register char *pb, register long n)
  53. {
  54.     register char c;
  55.  
  56.     while(n--) {
  57.         c = *pa;
  58.         *pa++ = *pb;
  59.         *pb++ = c;
  60.     }
  61. }
  62.  
  63. static _nsift(register char *base, register long i, register long n,
  64.                   register long size, register int (*cmp)())
  65. {
  66.     register long j;
  67.     register char *p;
  68.  
  69.     while((j = ((i << 1) + 1)) < n) {
  70.         p = (base+size*j);
  71.         if((j < (n - 1)) && ((*cmp)(p, p+size) < 0)) {
  72.             ++j;
  73.             p += size;
  74.         }
  75.         if((cmp)((base+size*i), p) < 0) {
  76.             _nswap((base+size*i), p, size);
  77.             i = j;
  78.         }
  79.         else
  80.             break;
  81.     }
  82. }
  83.  
  84. hsort(register char *base, register long num,
  85.        register long size, register int (*cmp)())
  86. /*
  87.  * Perform an N*log(N) heap-sort on an array starting at <base>
  88.  * containing <num> elements of <size> bytes each.  The function
  89.  * pointed to by <cmp> is used to compare elements.  Pointers to
  90.  * two items in the array are passed to the function, which must
  91.  * return a number representing their relationship as follows:
  92.  *     negative item1 < item2
  93.  *     0      item1 == item2
  94.  *     positive item1 > item2
  95.  * The hsort() function requires no extra storage, is not recursive,
  96.  * and has an almost constant N*log(N) sort time.  In the average
  97.  * case, it is about half as fast as qsort() on random data.  If
  98.  * portability is a concern, it should be noted that qsort() is
  99.  * almost always available, but hsort() is not.
  100.  */
  101. {
  102.     register long i, j;
  103.  
  104.     for(i = ((num >> 1) - 1); (i > 0); --i)
  105.         _nsift(base, i, num, size, cmp);
  106.     i = num;
  107.     while(i > 1) {
  108.         _nsift(base, 0, i--, size, cmp);
  109.         _nswap(base, (base+size*i), size);
  110.     }
  111. }
  112.  
  113. static int upcmp(SORTSTRUCT *a, SORTSTRUCT *b) /* aufsteigend */
  114. {
  115.     return(strcmp(a->str,b->str));
  116. }
  117.  
  118. static int dncmp(SORTSTRUCT *a, SORTSTRUCT *b) /* absteigend */
  119. {
  120.     register int ret;
  121.     ret=strcmp(a->str,b->str);
  122.     return(-ret);
  123. }
  124.  
  125. static int cupcmp(SORTSTRUCT *a, SORTSTRUCT *b) /* aufsteigend mit Spaltenangabe */
  126. {
  127.     return(strcmp(&a->str[col],&b->str[col]));
  128. }
  129.  
  130. static int cdncmp(SORTSTRUCT *a, SORTSTRUCT *b) /* absteigend mit Spaltenangabe */
  131. {
  132.     register int ret;
  133.     ret=strcmp(&a->str[col],&b->str[col]);
  134.     return(-ret);
  135. }
  136.  
  137. char __toupper(char c);
  138.  
  139. static int __stricmp(char *s, char *t)
  140. {
  141.     for(;(__toupper(*s) == __toupper(*t)); s++, t++)
  142.         if(*s == '\0')
  143.             return(0);
  144.     return(__toupper(*s) - __toupper(*t));
  145. }
  146.  
  147. static int upicmp(SORTSTRUCT *a, SORTSTRUCT *b) /* aufsteigend */
  148. {
  149.     return(__stricmp(a->str,b->str));
  150. }
  151.  
  152. static int dnicmp(SORTSTRUCT *a, SORTSTRUCT *b) /* absteigend */
  153. {
  154.     register int ret;
  155.     ret=__stricmp(a->str,b->str);
  156.     return(-ret);
  157. }
  158.  
  159. static int cupicmp(SORTSTRUCT *a, SORTSTRUCT *b) /* aufsteigend mit Spaltenangabe */
  160. {
  161.     return(__stricmp(&a->str[col],&b->str[col]));
  162. }
  163.  
  164. static int cdnicmp(SORTSTRUCT *a, SORTSTRUCT *b) /* absteigend mit Spaltenangabe */
  165. {
  166.     register int ret;
  167.     ret=__stricmp(&a->str[col],&b->str[col]);
  168.     return(-ret);
  169. }
  170.  
  171. long Wline(void *, void *);
  172.  
  173. void hndl_sort(WINDOW *wp, OBJECT *tree, LINESTRUCT **begcut, LINESTRUCT **endcut)
  174. {
  175.     long lines, chars;
  176.     LINESTRUCT *line;
  177.     register int ignore,grpblks;
  178.     register long i,k,x;
  179.     int exit_obj,a,b,c,d,e,f,g;
  180.     GRECT rect;
  181.     SORTSTRUCT *ss; /* Zeile  */
  182.     SORTSTRUCT *gs; /* Gruppe */
  183.     
  184.     static LINESTRUCT *grpbegcut=NULL, *grpendcut=NULL;
  185.     static long grpbegline=0, grpendline=0, grplen=0, grpline=0;
  186.     static int group=FALSE;
  187.     
  188.     extern long begline, endline;
  189.  
  190.     if(wp && *begcut && *endcut)
  191.     {
  192.         a=tree[SORTUP].ob_state;
  193.         b=tree[SORTDN].ob_state;
  194.         c=tree[SORTIGNO].ob_state;
  195.         sprintf(tree[SORTFROM].ob_spec.tedinfo->te_ptext,"%-4ld",Wline(wp,*begcut)+1);
  196.         sprintf(tree[SORTTO  ].ob_spec.tedinfo->te_ptext,"%-4ld",Wline(wp,*endcut)+1);
  197.         sprintf(tree[SORTCOL ].ob_spec.tedinfo->te_ptext,"%-3d",wp->w_state&COLUMN?(*begcut)->begcol+1:1);
  198.  
  199.       if(grpbegcut && grpendcut) /* erst jetzt Kriterium freigeben */
  200.             tree[SORTKRIT].ob_state &=~DISABLED;
  201.          
  202.         form_exopen(tree,0);
  203.         do
  204.         {
  205.             exit_obj=form_exdo(tree,0);
  206.             switch(exit_obj)
  207.             {
  208.                 case SORTHELP:
  209.                     form_alert(1,Asort[1]);
  210.                     objc_change(tree,exit_obj,0,tree->ob_x,tree->ob_y,tree->ob_width,tree->ob_height,tree[exit_obj].ob_state&~SELECTED,TRUE);
  211.                     break;
  212.                 case SORTLINE:
  213.                     if(!group) /* rücksetzen, wenn noch möglich */
  214.                     {
  215.                         tree[SORTKRIT].ob_state &= ~SELECTED;
  216.                         tree[SORTKRIT].ob_state |= DISABLED;
  217.                         objc_update(tree,SORTKRIT,0);
  218.                         tree[SORTEXTRA].ob_state &= ~SELECTED;
  219.                         tree[SORTEXTRA].ob_state |= DISABLED;
  220.                         objc_update(tree,SORTEXTRA,0);
  221.                     }
  222.                     break;
  223.                 case SORTGROUP:
  224. /*
  225.                     tree[SORTKRIT].ob_state &=~DISABLED;
  226.                     objc_update(tree,SORTKRIT,0);
  227. */
  228.                     tree[SORTEXTRA].ob_state &=~DISABLED;
  229.                     tree[SORTEXTRA].ob_state |= SELECTED;
  230.                     objc_update(tree,SORTEXTRA,0);
  231.                     break;
  232.             }
  233.         }
  234.         while(!(exit_obj==SORTABBR || exit_obj==SORTOK));
  235.         form_exclose(tree,exit_obj,0);
  236.         if(exit_obj==SORTABBR)
  237.         {
  238.             tree[SORTUP].ob_state=a;
  239.             tree[SORTDN].ob_state=b;
  240.             tree[SORTIGNO].ob_state=c;
  241.             tree[SORTLINE].ob_state|=SELECTED;
  242.             tree[SORTGROUP].ob_state&=~SELECTED;
  243.             tree[SORTKRIT].ob_state &=~SELECTED;
  244.             tree[SORTKRIT].ob_state |=DISABLED;
  245.             tree[SORTEXTRA].ob_state &=~SELECTED;
  246.             tree[SORTEXTRA].ob_state |=DISABLED;
  247.             grpbegcut=NULL;
  248.             grpendcut=NULL;
  249.             grpbegline=0L;
  250.             grpendline=0L;
  251.             grplen=0;
  252.             grpline=0;
  253.             group=FALSE;
  254.             return;
  255.         }
  256.         if(!group && (tree[SORTGROUP].ob_state & SELECTED) && !(tree[SORTKRIT].ob_state & SELECTED))
  257.         {
  258.             if(tree[SORTEXTRA].ob_state&SELECTED)
  259.                 form_alert(1,Asort[2]);
  260.             grpbegcut=*begcut;
  261.             grpendcut=*endcut;
  262.             grpbegline=begline;
  263.             grpendline=endline;
  264.             return;
  265.         }
  266.         if(!group && (tree[SORTGROUP].ob_state & SELECTED) &&  (tree[SORTKRIT].ob_state & SELECTED))
  267.         {
  268.             if(tree[SORTEXTRA].ob_state&SELECTED)
  269.                 form_alert(1,Asort[3]);
  270.             Wblksize(wp,*begcut,*endcut,&grplen,&chars);
  271.             group=TRUE;
  272.             return;
  273.         }
  274.         if(group && (tree[SORTKRIT].ob_state & SELECTED))
  275.         {
  276.             grpline=begline%grplen; /* Zeilenoffset zum Gruppenbeginn */
  277.         }
  278.         ignore=(tree[SORTIGNO].ob_state&SELECTED);
  279.         col=(*begcut)->begcol;
  280.         if(group)
  281.         {
  282.             Wblksize(wp,grpbegcut,grpendcut,&lines,&chars);
  283.             if((lines%grplen) == 0) /* ganzzahliges Vielfaches? */
  284.             {
  285.                 grpblks=lines/grplen; /* Anzahl der Blöcke */
  286. #if GEMDOS
  287.                 if((gs=Malloc(lines*sizeof(SORTSTRUCT)))!=NULL)
  288. #else
  289.                 if((gs=malloc(lines*sizeof(SORTSTRUCT)))!=NULL)
  290. #endif
  291.                 {
  292. #if GEMDOS
  293.                     if((ss=Malloc(grpblks*sizeof(SORTSTRUCT)))!=NULL)
  294. #else
  295.                     if((ss=malloc(grpblks*sizeof(SORTSTRUCT)))!=NULL)
  296. #endif
  297.                     {
  298.                         for(k=0,i=0,line=grpbegcut; i<lines && line!=grpendcut->next; i++,line=line->next)
  299.                         {
  300.                             if(tree[SORTGROUP].ob_state & SELECTED) /* ganze Gruppe */
  301.                             {
  302.                                 gs[i].str    = line->string; /* Gruppe sichern */
  303.                                 gs[i].used   = line->used;
  304.                                 gs[i].len    = line->len;
  305.                                 gs[i].effect = line->effect; /* Texteffekt */
  306.                             }
  307.                             if(((i-grpline)%grplen)==0) /* jede Zeile aus der Gruppe muß ganzzahlig teilbar sein */
  308.                             {
  309.                                 ss[k].str    = line->string;
  310.                                 ss[k].used   = line->used;
  311.                                 ss[k].len    = line->len;
  312.                                 ss[k].effect = line->effect;
  313.                                 ss[k].line   = k;
  314.                                 k++;
  315.                             }
  316.                         }
  317.  
  318.                         /* immer Spaltenblocksortierung */
  319.                         if(tree[SORTDN].ob_state & SELECTED) /* absteigend */
  320.                             hsort(ss,grpblks,sizeof(SORTSTRUCT),ignore?cdncmp:cdnicmp);
  321.                         else                                            /* aufsteigend */
  322.                             hsort(ss,grpblks,sizeof(SORTSTRUCT),ignore?cupcmp:cupicmp);
  323.  
  324.                         if(tree[SORTGROUP].ob_state & SELECTED) /* ganze Gruppe */
  325.                         {
  326.                             for(k=0,i=0,line=grpbegcut; i<lines && k<grpblks && line!=grpendcut->next; k++,i++)
  327.                             {
  328.                                 for(x=0; x<grplen && line; x++,line=line->next)
  329.                                 {
  330.                                     line->string=gs[ss[k].line*grplen+x].str;
  331.                                     line->used  =gs[ss[k].line*grplen+x].used;
  332.                                     line->len    =gs[ss[k].line*grplen+x].len;
  333.                                     line->effect=gs[ss[k].line*grplen+x].effect;
  334.                                 }
  335.                             }
  336.                         }
  337.                         else /* nur Gruppenkriterium */
  338.                         {
  339.                             for(k=0,i=0,line=grpbegcut; i<lines && line!=grpendcut->next; i++,line=line->next)
  340.                             {
  341.                                 if(((i-grpline)%grplen)==0) /* jede Zeile aus der Gruppe muß ganzzahlig teilbar sein */
  342.                                 {
  343.                                     line->string=ss[k].str;
  344.                                     line->used  =ss[k].used;
  345.                                     line->len    =ss[k].len;
  346.                                     line->effect=ss[k].effect;
  347.                                     k++;
  348.                                 }
  349.                             }
  350.                         }
  351. #if GEMDOS
  352.                         Mfree(ss);
  353. #else
  354.                         free(ss);
  355. #endif
  356.                         rect.g_x=wp->xwork;
  357.                         rect.g_y=wp->ywork+grpbegline*wp->hscroll-wp->hfirst;
  358.                         rect.g_w=wp->wwork;
  359.                         rect.g_h=(grpendline-grpbegline+1)*wp->hscroll;
  360.                         graf_mouse(M_OFF,0L);
  361.                         Wcursor(wp);
  362.                         Wredraw(wp,&rect);
  363.                         Wcursor(wp);
  364.                         graf_mouse(M_ON,0L);
  365.                         hide_blk(wp,*begcut, *endcut);
  366.                         undo.item=FALSE;
  367.                         wp->w_state|=CHANGED;
  368.                         Wcuron(wp);
  369.                         graf_mouse(ARROW,NULL);
  370.                     }
  371.                     else
  372.                         form_alert(1,Asort[0]);
  373. #if GEMDOS
  374.                     Mfree(gs);
  375. #else
  376.                     free(gs);
  377. #endif
  378.                 }
  379.                 else
  380.                     form_alert(1,Asort[0]);
  381.             }
  382.             else
  383.                 form_alert(1,Asort[4]);
  384.             tree[SORTLINE].ob_state|=SELECTED;
  385.             tree[SORTGROUP].ob_state&=~SELECTED;
  386.             tree[SORTKRIT].ob_state &=~SELECTED;
  387.             tree[SORTKRIT].ob_state |=DISABLED;
  388.             tree[SORTEXTRA].ob_state &=~SELECTED;
  389.             tree[SORTEXTRA].ob_state |=DISABLED;
  390.             grpbegcut=NULL;
  391.             grpendcut=NULL;
  392.             grpbegline=0L;
  393.             grpendline=0L;
  394.             grplen=0;
  395.             grpline=0;
  396.             group=FALSE;
  397.         }
  398.         else
  399.         {
  400.             Wblksize(wp,*begcut,*endcut,&lines,&chars);
  401. #if GEMDOS
  402.             if((ss=Malloc(lines*sizeof(SORTSTRUCT)))!=NULL)
  403. #else
  404.             if((ss=malloc(lines*sizeof(SORTSTRUCT)))!=NULL)
  405. #endif
  406.             {
  407.                 graf_mouse(BUSY_BEE,NULL);
  408.                 for(i=0,line=(*begcut); i<lines && line!=(*endcut)->next; i++,line=line->next)
  409.                 {
  410.                     ss[i].str =line->string;
  411.                     ss[i].used=line->used;
  412.                     ss[i].len =line->len;
  413.                     ss[i].effect =line->effect;
  414.                 }
  415.                 if(tree[SORTDN].ob_state & SELECTED) /* absteigend */
  416.                 {
  417.                     if(wp->w_state&COLUMN)
  418.                         hsort(ss,lines,sizeof(SORTSTRUCT),ignore?cdncmp:cdnicmp);
  419.                     else
  420.                         hsort(ss,lines,sizeof(SORTSTRUCT),ignore?dncmp:dnicmp);
  421.                 }
  422.                 else                                            /* aufsteigend */
  423.                 {
  424.                     if(wp->w_state&COLUMN)
  425.                         hsort(ss,lines,sizeof(SORTSTRUCT),ignore?cupcmp:cupicmp);
  426.                     else
  427.                         hsort(ss,lines,sizeof(SORTSTRUCT),ignore?upcmp:upicmp);
  428.                 }
  429.                 for(i=0,line=(*begcut); i<lines && line!=(*endcut)->next; i++,line=line->next)
  430.                 {
  431.                     line->string=ss[i].str;
  432.                     line->used  =ss[i].used;
  433.                     line->len    =ss[i].len;
  434.                     line->effect=ss[i].effect;
  435.                 }
  436. #if GEMDOS
  437.                 Mfree(ss);
  438. #else
  439.                 free(ss);
  440. #endif
  441.                 rect.g_x=wp->xwork;
  442.                 rect.g_y=wp->ywork+begline*wp->hscroll-wp->hfirst;
  443.                 rect.g_w=wp->wwork;
  444.                 rect.g_h=(endline-begline+1)*wp->hscroll;
  445.                 graf_mouse(M_OFF,0L);
  446.                 Wcursor(wp);
  447.                 Wredraw(wp,&rect);
  448.                 Wcursor(wp);
  449.                 graf_mouse(M_ON,0L);
  450.                 hide_blk(wp,*begcut, *endcut);
  451.                 undo.item=FALSE;
  452.                 wp->w_state|=CHANGED;
  453.                 Wcuron(wp);
  454.                 graf_mouse(ARROW,NULL);
  455.             }
  456.             else
  457.                 form_alert(1,Asort[0]);
  458.             tree[SORTLINE].ob_state|=SELECTED;
  459.             tree[SORTGROUP].ob_state&=~SELECTED;
  460.             tree[SORTKRIT].ob_state &=~SELECTED;
  461.             tree[SORTKRIT].ob_state |=DISABLED;
  462.             tree[SORTEXTRA].ob_state &=~SELECTED;
  463.             tree[SORTEXTRA].ob_state |=DISABLED;
  464.             grpbegcut=NULL;
  465.             grpendcut=NULL;
  466.             grpbegline=0L;
  467.             grpendline=0L;
  468.             grplen=0;
  469.             grpline=0;
  470.             group=FALSE;
  471.         }
  472.     }
  473. }ə
  474.